/**
 * 剑指 Offer 26. 树的子结构
 * https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
 */
const { createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
function compare(A, B) {
  if (A.val !== B.val) {
    return false;
  }
  if (B.left) {
    if (!A.left) {
      return false;
    }
    if (!compare(A.left, B.left)) {
      return false;
    }
  }
  if (B.right) {
    if (!A.right) {
      return false;
    }
    if (!compare(A.right, B.right)) {
      return false;
    }
  }
  return true;
}

/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
function dfs(A, B) {
  if (A.val === B.val) {
    if (compare(A, B)) {
      return true;
    }
  }
  if (A.left) {
    if (dfs(A.left, B)) {
      return true;
    }
  }
  if (A.right) {
    if (dfs(A.right, B)) {
      return true;
    }
  }
  return false;
}

/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
function isSubStructure(A, B) {
  if (!A || !B) {
    return false;
  }
  return dfs(A, B);
}

console.log(isSubStructure(
  createTreeNode([1, 2, 3]),
  createTreeNode([3, 1]),
) === false);
console.log(isSubStructure(
  createTreeNode([3, 4, 5, 1, 2]),
  createTreeNode([4, 1]),
) === true);
